洛谷 P15245 · 难度 NOI/NOI+/CTSC

背景

3s 1G

在洛谷上提交时，请使用不低于 C++17 的语言版本，并且无需添加 binary.h 头文件。

题目描述

小 H 在学习二进制运算的过程中遇到了一个经典问题：给定一个初始为 $0$ 的整数，每次操作可以将其乘 $2$ 或加 $1$，求将其变为某个给定正整数 $x$ 的最少操作次数。小 H 发现，这可以根据 $x$ 的二进制表示求出答案。

基于这个问题，小 H 提出了以下问题：给定两个正整数 $x,y$，定义一次操作为以下四种之一：

1. 将 $x$ 乘 $2$，即 $x\leftarrow 2x$；
2. 将 $y$ 乘 $2$，即 $y\leftarrow 2y$；
3. 将 $x$ 加 $1$，即 $x\leftarrow x+1$；
4. 将 $y$ 加 $1$，即 $y\leftarrow y+1$。

小 H 想知道最少需要多少次操作，才能使得 $x$ 和 $y$ 相等。你需要帮助小 H 求出操作次数的最小值。

【实现细节】

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序包含头文件 binary.h，即在程序开头加入以下代码：

#include "binary.h"

选手需要在提交的程序源文件 binary.cpp 中实现以下两个函数：

void init(int c, int t);

• $c,t$ 分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。
• 对于每个测试点，该函数会在程序开始运行时被交互库调用恰好一次。

long long binary(long long x, long long y);

• $x,y$ 表示给定的两个数。
• 该函数需要返回操作次数的最小值。
• 对于每个测试点，该函数会被交互库调用恰好 $t$ 次。

注意：在任何情况下，交互库运行所需时间均不会超过 $1.8$ 秒，所用内存为固定大小，且均不超过 $64$ MiB。

【测试程序方式】

试题目录下的 grader.cpp 是交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

选手可以在本题目下使用如下命令编译得到可执行程序：

g++ grader.cpp binary.cpp -o binary -O2 -std=c++14 -static

输入格式

对于编译得到的可执行程序：

• 可执行文件将从标准输入读入以下格式的数据：
  • 输入的第一行包含两个非负整数 $c,t$，分别表示测试点编号和测试数据组数。
  • 接下来依次为每组测试数据，对于每组测试数据：
    • 第一行包含两个正整数 $x,y$，表示给定的两个数。

输出格式

• 可执行文件将输出以下格式的数据至标准输出：
  • 对于每组测试数据，输出一行一个整数，表示操作次数的最小值。

说明/提示

【下发文件说明】

在本试题目录下：

1. grader.cpp 是提供的交互库参考实现。
2. binary.h 是头文件，选手不用关心具体内容。
3. template_binary.cpp 是提供的示例代码，选手可参考并实现自己的代码。

选手注意对所有下发文件做好备份。最终评测时只测试本试题目录下的 binary.cpp，对该程序以外文件的修改不会影响评测结果。

【数据范围】

对于所有测试数据，均有：

• $1\le t\le 5\times {10}^7$；
• $1\le x<y\le {10}^{18}$。

::cute-table

测试点编号	$t=$	$y\le$	特殊性质
$1\sim 4$	$10$	$10$	无
$5$	${10}^2$	${10}^2$	B
$6$	^	^	无
$7,8$	${10}^3$	${10}^3$	B
$9\sim 11$	^	^	无
$12$	$10$	${10}^6$	A
$13$	^	^	无
$14$	${10}^6$	^	A
$15$	^	^	B
$16$	^	^	无
$17,18$	^	${10}^{18}$	B
$19\sim 21$	^	^	无
$22\sim 24$	$2.5\times {10}^7$	^	^
$25$	$5\times {10}^7$	^	^

• 特殊性质 A：$y-x\le {10}^3$。
• 特殊性质 B：存在 $k\ge 1$ 与 $0\le z<2^k$ 满足 $y=x\times 2^k+z$。

【评分方式】

注意：

• 选手不应当通过非法方式获取交互库的内部信息，如直接与标准输入、输出流进行交互。此类行为将被视为作弊；
• 最终的评测交互库与样例交互库的实现不同。

本题首先会受到和传统题相同的限制，例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分。选手只能在程序中访问自己定义的变量以及交互库给出的变量，尝试访问其他地址空间可能导致编译错误或运行错误。

在上述条件基础上：

• 对于每个测试点，程序得到满分当且仅当每次调用 binary 函数时返回的答案均正确。

样例

样例 1

输入

0 5
1 2
1 5
3 6
7 33
5 9

输出

1
3
1
4
2